public class Solution494 {
    public int findTargetSumWays(int[] nums, int target) {
        int[][] f=new int[2][2005];
        f[1][1000]=1;
        for (int i=0;i<nums.length;i++) {
            for (int j=-1000;j<=1000;j++){
                f[i%2][j+1000]=0;
                if (j-nums[i]>=-1000){
                    f[i%2][j+1000]=f[(i+1)%2][j-nums[i]+1000];
                }
                if (j+nums[i]<=1000){
                    f[i%2][j+1000]+=f[(i+1)%2][j+nums[i]+1000];
                }
            }
        }
        return f[(nums.length-1)%2][target+1000];
    }

    public static void main(String[] args) {
        System.out.println(new Solution494().findTargetSumWays(new int[]{1,1,1,1,1},3));
    }
}
